from timeit import Timer

import sys
import math


def Primes(max, limit = -1):
    """ Returns a list of primes. """    
    # Generate list of primes
    primes = [2]
    
    #create function once
    full = lambda e: e >= limit
    if limit == -1:
        full = lambda e: False
    
    for x in xrange(3,max, 2):
        # exit if we have a complete list
        if full(len(primes)):
            break
        # if divisible by a prime, stop
        for p in primes:
            if x % p == 0:
                break
            elif p*p > x + 6:
                primes.append(x)
                break
        # if not divisible then add to list
        else:
            primes.append(x)

    return primes

""" Given a number n, it gives Proper Divisors of n
   (numbers less than n which divide evenly into n.)
   Input: n = natural number
   Output: list of proper divisors of n
""" 
def Divisors(n):
    d = set([1])
    p, r = 2, n/2
    while p <= r:
        if n % p == 0:
            r = n/p
            d.add(p)
            d.add(r)
            
        p += 1
        
    return list(d)